⟸ Go Back ⟸

Exercise 11 (Homework 2).

(regular languages, union, finite set)

Finite languages are regular

1. Show that for every word w, the language \{w\} is regular.

2. Show that every finite language, i.e. any language consisting only of a finite number of words, is regular.

3. A language L is co-finite if its complement \overline L is finite. Show that if a language is co-finite, then it is regular.

4. Show that the language L=\{0^n \mid \text{the decimal expansion of $\pi$ contains $n$ consecutive $0$s}\} is regular.

   Hint

   No knowledge about any property of the decimal expansion of \pi is needed (apart from being infinite). Think instead of a nonconstructive proof by cases.

5. A crucial part of the definition of DFAs is that they are only allowed to have a finite number of states. Show that the definition would become trivial if DFAs were allowed to have an infinite number of states, in the sense that every language (say over the alphabet \{a,b\}) could be recognized by a DFA if we allowed it to have an infinite number of states.